import java.util.*;


/**
 * Algorithms
 *
 * @author Darksiderl
 * @date 2018/3/3
 */
public class Algorithms {

    public static void main(String[] args) {
//        int a[] = {1, 7, 12, 13, 1, 3};
//        int[] ints = twoSumQuick(a, 9);
//        for (int i : ints) {
//            System.out.println(i);
//        }
        //1 2 3
        //3 2 1
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(3);

        ListNode l2 = new ListNode(3);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(1);

        ListNode node = addTwoNumbers(l1, l2);
//        ListNode currentNode = node;
//        System.out.println(node.val);
//        while (currentNode.next != null) {
//            System.out.println(currentNode.next.val);
//            currentNode = currentNode.next;
//        }

    }


//    给定一个整数数列，找出其中和为特定值的那两个数。
//    你可以假设每个输入都只会有一种答案，同样的元素不能被重用。
//    示例:
//    给定 nums = [2, 7, 11, 15], target = 9
//    因为 nums[0] + nums[1] = 2 + 7 = 9
//    所以返回 [0, 1]

    //o(n2)
    public static int[] twoSum(int[] origin, int target) {

        for (int i = 0; i < origin.length; i++) {
            for (int j = i + 1; j < origin.length; j++)
                if (origin[i] <= target && origin[j] <= target) {
                    if ((origin[i] + origin[j]) == target) {
                        return new int[]{i, j};
                    }
                }
        }

        return null;
    }

    //o(n)
    public static int[] twoSumQuick(int[] origin, int target) {
        Map<Integer, Integer> map = new HashMap();
        for (int i = 0; i < origin.length; i++) {
            map.put(origin[i], i);
        }

        for (int i = 0; i < origin.length; i++) {
            int computeResult = target - origin[i];
            if (map.containsKey(computeResult) && map.get(computeResult) != i) {
                return new int[]{i, map.get(computeResult)};
            }
        }
        throw new IllegalArgumentException("no two sum solution");
    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();

        String sl1 = "";
        String sl2 = "";

        list1.add(l1.val);
        list2.add(l2.val);

        ListNode currentNode1 = l1;
        ListNode currentNode2 = l2;
        while (currentNode1.next != null) {
            list1.add(currentNode1.next.val);
            currentNode1 = currentNode1.next;
        }
        while (currentNode2.next != null) {
            list2.add(currentNode2.next.val);
            currentNode2 = currentNode2.next;
        }

        Collections.reverse(list1);
        Collections.reverse(list2);

        for (Integer i1:list1) {
            sl1 += i1;
            System.out.println(i1);
        }

        for (Integer i2:list2) {
            System.out.println(i2);
            sl2 += i2;
        }



        Integer isum = Integer.valueOf(sl1) + Integer.valueOf(sl2);
        ListNode node = new ListNode(isum%10);
        ListNode currentNode = node;

        isum = isum/10;
        int length = String.valueOf(isum).length();
        for (int i = 1;i < length;i++){
            currentNode.next = new ListNode(isum % 10);
            isum = isum / 10;
            currentNode = currentNode.next;

        }

        return node;
    }

}
